package com.cab.pack.demo;

import com.alibaba.fastjson.JSON;

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.nio.charset.StandardCharsets;
import java.util.ArrayList;
import java.util.List;

/**
 * @author: lanyanhua
 * @date: 2021/8/2 7:37 下午
 * @Description:
 */
public class PackTest {

    public List<Label> labels = new ArrayList<>();//特征标签
    public List<Goods> goodsAttrs = new ArrayList<>();//商品属性


    public static void main(String[] args) {
        PackTest test = new PackTest();
        test.getData("/Users/lanyanhua/Downloads/knapsack-algorithm/src/main/resources/data/data.txt");
        //总量
        List<Integer> counts = new ArrayList<>();
        for (int i = 2; i < test.labels.size(); i++) {
            counts.add(test.labels.get(i).count);
        }
        List<Detailed> res = test.baseList(test.goodsAttrs, counts);
        //结果输出
        System.out.println(JSON.toJSONString(res));
        System.out.println();
        for (int i = 2; i < test.labels.size(); i++) {
            Label label = test.labels.get(i);
            System.out.println("背包"+label.label + ":" + label.count);
        }
        System.out.println("可最大价值：" + test.v(res));
        System.out.println("名称\t数量\t价值\t明细总量");
        for (Detailed d : res) {
            Goods goods = d.goods;
            System.out.print(goods.name + "\t" + d.number + "\t" + d.value+"\t");
            //明细
            for (int i = 0; i < goods.attrs.size(); i++) {
                System.out.print(test.labels.get(i + 2).label + ":" + goods.attrs.get(i) * d.number+"\t");
            }
            System.out.println();
        }
    }

    /**
     * 最佳清单
     *
     * @param goodsList 商品列表
     * @param count     剩余容量
     * @return 最佳清单
     */
    public List<Detailed> baseList(List<Goods> goodsList, List<Integer> count) {
        Goods goods = goodsList.get(0);
        //获取当前商品从 0到最大存放数量对应的剩余容量
        List<List<Integer>> counts = goodsMaxNum(goods.attrs, count);
        if (counts.size() == 0) {
            //已经放不下了
            return new ArrayList<>();
        }
        //商品只剩余一种直接计算最大可存放数量
        if (goodsList.size() == 1) {
            //结束递归 名称 数量 价值
            List<Detailed> baseList = new ArrayList<>();
            //size-1 0下标对应的商品也是0个不算
            int number =counts.size()-1;
            baseList.add(new Detailed(goods, number, goods.value * number));
            return baseList;
        }
        //最佳清单
        List<Detailed> baseList = null;
        //后面的商品
        List<Goods> goods1 = goodsList.subList(1, goodsList.size());
        //0 - maxNum 表示当前商品装了几个
        for (int i = 0; i < counts.size(); i++) {
            Detailed detailed = new Detailed(goods, i, goods.value * i);
            //获取容量
            List<Integer> count1 = counts.get(i);
            //计算后面商品的最佳清单
            List<Detailed> temp = baseList(goods1, count1);
            //数量大于1添加到清单
            if (i > 0) {
                temp.add(detailed);
            }
            //大于替换
            if (baseList == null || v(temp) > v(baseList)) {
                baseList = temp;
            }
        }
        return baseList;
    }

    public int v(List<Detailed> list) {
        return list.stream().mapToInt(i -> i.value).sum();
    }


    /**
     * 商品剩余容量的关系
     *
     * @param attrs 商品属性
     * @param count 剩余容量
     */
    public List<List<Integer>> goodsMaxNum(List<Integer> attrs, List<Integer> count) {
        List<List<Integer>> res = new ArrayList<>();
        //取最大存放数量
        int max = getMax(attrs, count);
        if(max==0){
            return new ArrayList<>();
        }
        //i 商品数量
        for (int i = 0; i <= max; i++) {
            List<Integer> countTemp = new ArrayList<>();
            //遍历每个属性
            for (int i1 = 0; i1 < attrs.size(); i1++) {
                //i个商品的属性值
                Integer a = i * attrs.get(i1);
                //剩余值
                countTemp.add(count.get(i1) - a);
            }
            res.add(countTemp);
        }
        return res;
    }


    /**
     * 取当前商品最大数量
     *
     * @param attrs 属性
     * @param count 剩余数量
     * @return 最大值
     */
    public int getMax(List<Integer> attrs, List<Integer> count) {
        int max = -1;
        for (int i = 0; i < attrs.size(); i++) {
            int temp = count.get(i) / attrs.get(i);
            if (max == -1 || temp < max) {
                max = temp;
            }
        }
        return max;
    }

    private void getData(String path) {
        String str;
        try {
            FileInputStream fis = new FileInputStream(path);
            InputStreamReader isr = new InputStreamReader(fis, StandardCharsets.UTF_8);
            BufferedReader in = new BufferedReader(isr);
            //标签
            str = in.readLine();
            String[] label = str.split(",");
            str = in.readLine();
            String[] count = str.split(",");
            for (int i = 0; i < label.length; i++) {
                labels.add(new Label(label[i], Integer.valueOf(count[i])));
            }
            //商品数据
            while ((str = in.readLine()) != null) {
                //数据处理
                String[] split = str.split(",");
                Goods goods = new Goods();
                goods.name = split[0];
                goods.value = Integer.parseInt(split[1]);
                List<Integer> attrs = new ArrayList<>();
                for (int i = 2; i < split.length; i++) {
                    attrs.add(Integer.parseInt(split[i]));
                }
                goods.attrs = attrs;
                goodsAttrs.add(goods);
            }
            in.close();
        } catch (Exception e) {
            throw new RuntimeException("读取数据文件失败！" + e.getMessage());
        }
    }

    public static class Label {
        //标签
        public String label;
        //总量
        public Integer count;

        public Label(String label, Integer max) {
            this.label = label;
            this.count = max;
        }
    }

    public static class Detailed {
        //商品
        public Goods goods;
        //数量
        public int number;
        //价值
        public int value;

        public Detailed(Goods goods, int number, int value) {
            this.goods = goods;
            this.number = number;
            this.value = value;
        }
    }

    public static class Goods {
        //名称
        public String name;
        //价值
        public int value;
        //属性
        public List<Integer> attrs;
    }
}
